В данном разделе мы рассмотрим широкое семейство алгоритмов, позволяющее делать улучшения в способах введения регуляризации, которые невозможно добиться в классическом градиентном спуске.

Полезные ссылки

Все написанное ниже (за исключением вывода AdaGrad) — сокращенный пересказ обзора H. Brendan McMahan A Survey of Algorithms and Analysis for Adaptive Online Learning. Везде, где мы обозначаем Lemma 4, Theorem 10 и т.д. — мы ссылаемся на соответствующие теоремы из этой статьи. То же самое с доказательствами: если мы что-то опускаем, подробности можно найти в обзоре

Интуитивный вывод AdaGrad взят из статьи Adaptive Subgradient Methods for Online Learning and Stochastic Optimization . Вместо оригинальных оценок на метод Regularized Dual Averaging, требующих дополнительных понятий вроде двойственности по Фенхелю, мы использовали аналогичную оценку из обзора выше, сохранив все рассуждения автора. Опять же — строгое доказательство оценок на regret для AdaGrad есть в этом обзоре.

Синтаксический сахар

В выкладках очень часто используются суммы, и без сокращенных обозначений читать их невозможно. В литературе про онлайн-обучение приняты вот такие сокращения:

  • r0:t(w)=s=0trs(w)\color{#348FEA}{r_{0:t}(w)} = \sum\limits_{s=0}^tr_s(w);
  • Особо отметим обозначение r0:t(wt)=s=0trs(wt)\color{#348FEA}{r_{0:t}(w_t)} = \sum\limits_{s=0}^tr_s(w_t), т.е. точка wtw_t фиксирована и не меняется с индексацией в сумме;
  • h0:t(w)=f1:t(w)+r0:t(w)\color{#348FEA}{h_{0:t}(w)} = f_{1:t}(w) + r_{0:t}(w) (обычно это будет сумма функции потерь и регуляризатора);
  • gt\color{#348FEA}{g_t} — субградиент функции ft(w)f_t(w) в точке wtw_t.

Аддитивные регуляризаторы

В новых обозначениях описанные выше алгоритмы примут вид:

  • Adaptive FTRL: wT=argminw[f1:t(w)+RT(w)]w_T = arg\min\limits_w \Big[f_{1:t}(w) + R_T(w)\Big]
  • Adaptive Linearized FTRL: wT=argminw[f1:t(wt)Tw+RT(w)]w_T = arg\min\limits_w \Big[\nabla f_{1:t}(w_t)^Tw + R_T(w)\Big]

Опишем условия, накладываемые нами на алгоритм. В обзоре они называются Setting 1.

Setting 1

От функций RT(w)R_T(w) мы потребуем, чтобы они представлялись в виде:

RT(w)=t=0Trt(w)=r0:T(w)R_T(w) = \sum\limits_{t=0}^Tr_t(w) = r_{0:T}(w)

Слагаемые должны удовлетворять следующим условиям:

  1. Все rt(w)r_t(w) выпуклы (вниз);
  2. rt(w)0r_t(w) \geq 0;
  3. w0=argminwr0(w)w_0 = arg\min\limits_w r_0(w).

Также наложим следующие требования на h1:t=f1:t(w)+r0:t(w)h_{1:t} = f_{1:t}(w) + r_{0:t}(w):

  1. Область определения h1:th_{1:t} — непустое множество. Это требование может показаться странным, но при желании можно придумать пример h1:th_{1:t} с пустой областью определения: достаточно взять несколько регуляризаторов-проекций Iχ(w)I_{\chi}(w) на непересекающиеся выпуклые множества (подробнее о таких регуляризаторах мы расскажем в одном из следующих разделов);
  2. Субдифференциал wtft(w)\partial_{w_t} f_t(w) в точке wtw_t непуст.

Классы алгоритмов FTRL

Будем рассматривать аддитивные регуляризаторы rt(w)r_t(w) из двух семейств в зависимости от того, где у них минимум:

  • FTRL-Centered: argminwrt(w)=w0arg\min\limits_w r_t(w) = w_0;
  • FTRL-Proximal: argminwrt(w)=wtarg\min\limits_w r_t(w) = w_t;
  • Composite Objective: смешение первых двух семейств.

Обратите внимание: название Proximal напрямую связано с проксимальным градиентным спуском (ссылка на учебник с проксимальными методами). В обоих случаях мы накладываем регуляризатор в текущей точке wtw_t.

Обратите внимание: для Proximal регуляризаторов зачастую требуют выполнения более сильного условия: rt(wt)=0r_t(w_t) = 0. Это не такое уж и серьёзное ограничение: все разумные Proximal регуляризаторы (например, wwt2\vert\vert w - w_t\vert\vert^2) ему удовлетворяют.

Обратите внимание: у обоих семейств есть значимые высокоцитируемые статьи

  • FTRL-Centered: метод Regularized Dual Averaging. Статья получила премию Test of Time Award на NeurIPS 2021, так как огромное количество последующих громких результатов (тот же AdaGrad) напрямую основывались на этих результатах. В названии Dual Averaging под dual average имеется в виду 1tg1:t\frac1t g_{1:t}, то есть среднее по градиентам. Кардинально других техник оценок regret там нет, обзор McMahan строго улучшает все доступные там результаты.
  • FTRL-Proximal: самая известная статья от гугла Ad Click Prediction. Известна она скорее потому, что там выписаны формулы и объяснено, как правильно реализовывать метод для large-scale задач с результатами применения различных дополнительных инженерных идей. Это хороший инженерный обзор, а не математическая статья.

Рассмотрим отдельно каждую из разновидностей алгоритмов

FTRL-Centered

Задача оптимизации имеет вид

wt+1=argminwh0:t=argminw[g1:tTw+r0:t(w)],w_{t+1} = arg\min\limits_{w} h_{0:t} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + r_{0:t}(w)\Big],

где rt(w)r_t(w) таковы, что

argminwrt(w)=w0arg\min\limits_w r_t(w) = w_0

Пример: Рассмотрим SGD с фиксированным learning rate и стартом в точке 00. Положим

r1(w)=12ηw22r_1(w) = \frac{1}{2\eta}\vert\vert w\vert\vert_2^2

rt(w)=0,t>0r_t(w) = 0, \quad t > 0

w0=0w_0 = 0

wt+1=argminw[g1:tTw+12ηw22].w_{t+1} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\Big].

Как мы уже знаем, итеративное обновление весов будет иметь вид

wt+1=wtηgt.w_{t+1} = w_t - \eta g_t.

FTRL-Proximal

Задача имеет похожий вид

wt+1=argminwh0:t=argminw[g1:tTw+r0:t(w)],w_{t+1} = arg\min\limits_{w} h_{0:t} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + r_{0:t}(w)\Big],

но rt(w)r_t(w) выбираются так, чтобы

argminwrt(w)=wtarg\min\limits_w r_t(w) = w_t

Пример: Рассмотрим SGD с убывающим learning rate:

ηt=αt\eta_t = \frac{\alpha}{\sqrt{t}}

σt=1ηt1ηt1\sigma_t = \frac{1}{\eta_t} - \frac{1}{\eta_{t-1}}

Подробный вывод связи σt\sigma_t и ηt\eta_t мы приведём в одном из следующих разделов, а сейчас просто приведём результат:

rt(w)=σtwwtw2r_t(w) = \sigma_t\vert\vert w - w_t\vert\vert_w^2

wt+1=argminw[g1:tTw+s=1tσswwsw2]w_{t+1} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + \sum\limits_{s=1}^t\sigma_s \vert\vert w - w_s\vert\vert_w^2\Big]

wt+1=wtηtgt=wtαtgtw_{t+1} = w_t - \eta_t g_t = w_t - \frac{\alpha}{\sqrt{t}} g_t

Обратите внимание: как правило, на практике Proximal методы работают лучше. Интуитивно, центрирование в недавних точках вместо

Composite-Objective FTRL

Рассмотрим смесь центрированных и проксимальных регуляризаторов:

wt+1=argminwh0:t=argminw[g1:tTw+ψ0:t(w)+r0:t(w)],w_{t+1} = arg\min\limits_{w} h_{0:t} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + \psi_{0:t}(w) + r_{0:t}(w)\Big],

где rt(w)r_t(w) и ψt(w)\psi_t(w) таковы, что

argminwrt(w)=wtarg\min\limits_w r_t(w) = w_t

argminwψt(w)=w0arg\min\limits_w \psi_t(w) = w_0

Пример: FTRL-Proximal с L1 и L2 регуляризацией

wt+1=argminw[g1:tTw+λ1,tw1+λ2,tww2+s=1tσswws22]w_{t+1} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + \lambda_{1,t}\vert\vert w\vert\vert_1 + \lambda_{2,t}\vert\vert w\vert\vert_w^2 + \sum\limits_{s=1}^t\sigma_s \vert\vert w - w_s\vert\vert_2^2\Big]

Обратите внимание: как правило, центрированные регуляризаторы в довесок к проксимальным вводят уже не для «дополнительной стабилизации» алгоритма, а для наложения ограничений на решение ww.

Обратите внимание: наиболее правильные и хорошо работающие на практике способы подбора коэффициентов λ1,t\lambda_{1,t} и λ2,t\lambda_{2,t} мы приведём в параграфе про учет дополнительной L1L_1 и L2L_2 регуляризации.

Гарантии сходимости для алгоритмов FTRL

В этом разделе мы обсудим теоретические оценки на скорость сходимости алгоритма FTRL или, что то же самое, на скорость убывания maxRegret.

Напомним формулу:

maxRegret(T)=maxw[t=1Tft(wt)f1:T(w)]maxRegret(T) = \max\limits_{w^*}\left[ \sum\limits_{t=1}^Tf_t(w_t) - f_{1:T}(w^*)\right]

Чтобы делать оценки на maxRegret, нужно пытаться оценить асимптотику ряда, каждое слагаемое которого — это решение сложной оптимизационной задачи minwf1:t(w)\min\limits_w f_{1:t}(w) с произвольными функциями ft(w)f_t(w). Работать с такой сущностью крайне сложно. Наша основная цель — сделать верхнюю оценку на regret, в которой не будет этого члена.(???)

Strong FTRL Lemma (Lemma 4)

  1. Пусть ft(w)f_t(w) — последовательность произвольных (не обязательно) функций;
  2. Пусть rt(w)r_t(w) — последовательность выпуклых неотрицательных регуляризаторов;
  3. Пусть также wt+1=argminwh0:t(w)w_{t+1} = arg \min\limits_w h_{0:t}(w) всегда определен (относительно слабые условия 1-2 требуют от нас это явно проговорить);
    Тогда алгоритм, выбирающий wt+1w_{t+1} по правилу (3), удовлетворяет неравенству

RegretT(w)r0:T(w)+t=1T[h0:t(wt)h0:t(wt+1)rt(wt)12]Regret_T(w^*) \leq r_{0:T}(w^*) + \sum\limits_{t=1}^T \left[h_{0:t}(w_t) - h_{0:t}(w_{t+1}) - r_t(w_t)\vphantom{\frac12}\right]

Из чего состоит эта лемма?

  1. Слагаемое r0:T(w)r_{0:T}(w^*) — это суммарная регуляризация в точке ww^*. Совсем избавиться от вхождения ww^* не получится, но мы можем выбирать регуляризатор так, чтобы оценить сверху r0:T(w)r_{0:T}(w^*) было не очень сложно.

  2. Каждое слагаемое суммы t=1T[h0:t(wt)h0:t(wt+1)12]\sum\limits_{t=1}^T \left[h_{0:t}(w_t) - h_{0:t}(w_{t+1})\vphantom{\frac12}\right] отражает, насколько улучшается tt-й лосс h0:th_{0:t} при замене wtw_t на wt+1=argminwh0:t(w)w_{t+1} = arg \min\limits_w h_{0:t}(w). Поведение разностей h0:t(wt)h0:t(wt+1)h_{0:t}(w_t) - h_{0:t}(w_{t+1}) характеризует стабильность алгоритма. Мы ожидаем, что при больших tt у хорошо сходящегося алгоритма на очередном шаге wtw_t будет достаточно близок к оптимуму wt+1w_{t+1}, то есть вся сумма будет меняться всё медленнее, и её получится разумно оценить. Пример ситуации, когда это не так, мы уже видели, когда рассматривали FTL без регуляризации для линейной функции потерь (там всё было максимально нестабильно и расходилось). К счастью, введение регуляризации обычно помогает добиться стабильности.

Обе компоненты неразрывно связаны. Добавляя регуляризацию, мы увеличиваем первую компоненту, но улучшает стабильность алгоритма, чем уменьшаем вторую, и наоборот.

Обратите внимание: в условиях леммы допускаются невыпуклые ft(w)f_t(w), и это позволяет применять её в весьма общей ситуации. Впрочем, все наши последующие выкладки все-таки будут опираться на выпуклость ft(w)f_t(w).

Доказательство Strong FTRL Lemma

Преобразуем выражение для regret:

regret(T)=t=1Tft(wt)f1:T(w)=regret(T) = \sum\limits_{t=1}^Tf_t(w_t) - f_{1:T}(w^*) =

=t=0Tht(wt)h0:T(w)t=0Trt(wt)+r0:T(w)=()= \sum\limits_{t=0}^Th_t(w_t) - h_{0:T}(w^*) - \sum_{t=0}^Tr_t(w_t) + r_{0:T}(w^*) = (\ast)

Вспомним, что

wt+1=argminwh0:t(w),w_{t+1} = arg \min\limits_w h_{0:t}(w),

откуда

h0:t(w)h0:t(wt+1).h_{0:t}(w^*) \geq h_{0:t}(w_{t+1}).

Поэтому выражение выше мы можем оценить как

()t=0Tht(wt)h0:T(wt+1)t=0Trt(wt)+r0:T(w)=()(\ast)\leq \sum\limits_{t=0}^Th_t(w_t) - h_{0:T}(w_{t+1}) - \sum_{t=0}^Tr_t(w_t) + r_{0:T}(w^*) = (\ast\ast)

Теперь займёмся первыми двумя компонентами

t=0Tht(wt)h0:T(wt+1)=\sum\limits_{t=0}^Th_t(w_t) - h_{0:T}(w_{t+1}) =

=h0(w0)+t=1T[h0:t(wt)h0:t1(wt)12]h0:T(wT+1)= h_0(w_0) + \color{#E06A27}{\sum\limits_{t=1}^T}\left[h_{0:t}(w_t) \color{#E06A27}{- h_{0:t-1}(w_t)} \vphantom{\frac12}\right] \color{#E06A27}{- h_{0:T}(w_{T+1})}

Посмотрим повнимательнее на рыжие слагаемые:

t=1Th0:t1(wt)+h0:T(wT+1)=t=1Ti=0t1hi(wt)+i=0Thi(wT+1)=\sum\limits_{t=1}^T h_{0:t-1}(w_t) + h_{0:T}(w_{T+1}) = \color{#348FEA}{\sum\limits_{t=1}^T \sum\limits_{i=0}^{t-1}h_i(w_t)} + \sum\limits_{i=0}^T h_i(w_{T+1}) =

=12s=t1=s=0T1i=0shi(ws+1)+i=0Thi(wT+1)== \left|\vphantom{\frac12}\color{#348FEA}{s = t - 1}\right| = \color{#348FEA}{\sum\limits_{s=0}^{T-1} \sum\limits_{i=0}^{s}h_i(w_{s+1})} + \sum\limits_{i=0}^T h_i(w_{T+1}) =

=t=0Ti=0thi(wt+1)=t=0Th0:t(wt+1)==\sum\limits_{t=0}^{T}\sum\limits_{i=0}^{t}h_i(w_{t+1}) = \sum\limits_{t=0}^Th_{0:t}(w_{t+1}) =

=h0(w1)+t=1Th0:t(wt+1)= h_0(w_1) + \sum\limits_{t=1}^Th_{0:t}(w_{t+1})

Подставим это:

()=h0(w0)+t=1Th0:t(wt)h0(w1)t=1Th0:t(wt+1)t=0Trt(wt)+r0:T(w)(\ast\ast) = h_0(w_0) + \sum\limits_{t=1}^Th_{0:t}(w_t) - h_0(w_1) - \sum\limits_{t=1}^Th_{0:t}(w_{t+1}) - \sum_{t=0}^Tr_t(w_t) + r_{0:T}(w^*) \leq

h0(w0)+r0:T(w)+t=1T[h0:t(wt)h0:t(wt+1)rt(wt)12].\leq h_0(w_0) + r_{0:T}(w^*) + \sum\limits_{t=1}^T \left[h_{0:t}(w_t) - h_{0:t}(w_{t+1}) - r_t(w_t)\vphantom{\frac12}\right].

Здесь мы снова воспользовались тем, что h0(w1)=r0(w1)0h_0(w_1) = r_0(w_1)\geq 0, а также сократили h0(w0)=r0(w0)h_0(w_0) = r_0(w_0).

Лемма доказана.

Теоретические оценки на Regret (regret bounds)

Ниже мы представим теоремы 1,2 и 10 из обзора McMahan. Они дают оценки на regret в немного разных исходных предположениях и для разных типов регуляризаторов; асимптотика regret в каждом из случаев O(T)O(\sqrt{T}), хотя константы будут различными. О важности констант в сходимости мы поговорим в одной из следующих параграфов, когда будем разбирать метод AdaGrad. В самом конце параграфа мы обсудим, какие оценки получаются для линеаризованного regret. А в следующем параграфе мы займёмся выводом конкретных алгоритмов FTRL для разных видов регуляризаторов.

Мы не будем полностью пересказывать обзор (если вам стало интересно, рекомендуем прочитать его самостоятельно) и докажем в качестве примера теорему 2, а для остальных приведём лишь формулировки.

Напоминание из выпуклого анализа

Определение Выпуклая функция ψ(x)\psi(x) называется σ\sigma-сильно выпуклой по отношению к некоторой норме \vert\vert \cdot\vert\vert, если выполнено

gψ(y)ψ(x)ψ(y)+gT(xy)+σ2xy2\forall g \in \partial \psi(y) \quad \psi(x) \geq \psi(y) + g^T(x-y) + \frac{\sigma}{2}\vert\vert x-y\vert\vert^2

Определение Двойственной нормой \vert\vert \cdot\vert\vert_* по отношению к норме \vert\vert \cdot\vert\vert называется

x=supy:y1xTy\vert\vert x\vert\vert_* = \sup\limits_{y:\vert\vert y\vert\vert \leq 1} x^Ty

Физический смысл

Эта норма у нас возникнет в контексте работы с градиентами. С одной стороны, конечно, градиент gt=wtftg_t = \nabla_{w_t}f_t — это вектор, но по сути он играет роль линейной функции wgtTww\mapsto g_t^Tw, и кажется логичным определять для него норму именно как для линейной функции, то есть как для элемента двойственного пространства, состоящего из ограниченных линейных функций на исходном пространстве.

Как можно определить норму отображения? Самый, пожалуй, естественный вариант — это рассмотреть операторую норму относительно \vert\vert \cdot\vert\vert:

x=supy0xTyy,\vert\vert x\vert\vert_* = \sup\limits_{y\leq 0} \frac{|x^Ty|}{\vert\vert y\vert\vert},

Это формула верна, если пространство, в котором живут xx и yy ненулевое (впрочем, нулевое мы вряд ли рассматриваем). Можно показать, что это выражение равно supy:y1xTy\sup\limits_{y:\vert\vert y\vert\vert \leq 1} x^Ty.

Построенная норма называется двойственной к норме \vert\vert\cdot\vert\vert на исходном пространстве.

Более подробно о σ\sigma-сильной выпуклости и двойственных нормах вы можете почитать, например, в книге Boyd, 2004, Convex Optimization.

Теорема 1. General FTRL Bound

Пусть

  • Обновление параметров происходит по правилу

wt+1=argminwh0:t=argminw[g1:tTw+r0:t(w)];w_{t+1} = arg\min\limits_{w} h_{0:t} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + r_{0:t}(w)\Big];

  • Выполнены все условия Setting 1;
  • Регуляризатор rt(w)r_t(w) выбирается так, чтобы выражение h0:t(w)+ft+1(w)=r0:t(w)+f1:t+1(w)h_{0:t}(w) + f_{t+1}(w) = r_{0:t}(w) + f_{1:t+1}(w) было 1-сильно выпукло по отношению к некоторой норме t\vert\vert \cdot\vert\vert_{t} (возможно, своей на каждом шаге).

Тогда

RegretT(w)r0:T1(w)+12t=1Tgt(t1),2,Regret_T(w^*) \leq r_{0:T-1}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{(t-1),*}^2,

где (t1),\vert\vert \cdot\vert\vert_{(t-1),*} — норма, двойственная к норме (t1)\vert\vert \cdot\vert\vert_{(t-1)}.

Теорема 2. FTRL-Proximal Bound

Пусть

  • Обновление параметров происходит по правилу

wt+1=argminwh0:t=argminw[g1:tTw+r0:t(w)];w_{t+1} = arg\min\limits_{w} h_{0:t} = arg\min\limits_{w}\Big[ g_{1:t}^Tw + r_{0:t}(w)\Big];

  • Выполнены все условия Setting 1;
  • Все регуляризаторы rt(w)r_t(w) лежат в семействе FTRL-Proximal, причём rt(wt)=0r_t(w_t) = 0 для всех tt;
  • rt(w)r_t(w) выбирается так, чтобы выражение h0:t(w)=r0:t(w)+f1:t(w)h_{0:t}(w) = r_{0:t}(w) + f_{1:t}(w) было 1-сильно выпукло по отношению к некоторой норме t\vert\vert \cdot\vert\vert_t (возможно, своей на каждом шаге).

Тогда

RegretT(w)r0:T(w)+12t=1Tgtt,2,Regret_T(w^*) \leq r_{0:T}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{t,*}^2,

где t,\vert\vert \cdot\vert\vert_{t,*} — норма, двойственная к норме t\vert\vert \cdot\vert\vert_{t}.

Теорема 10. Composite Objective FTRL-Proximal Bound

Пусть

  • Обновление параметров происходит по правилу

wt+1=argminwh0:t=argminw[g1:tTw+α1:tΨ(w)+r0:t(w)];w_{t+1} = arg\min\limits_{w} h_{0:t} = arg\min\limits_{w} \Big[g_{1:t}^Tw + \alpha_{1:t}\Psi(w) + r_{0:t}(w)\Big];

  • Выполнены все условия Settning 1;
  • h^t(w)=ft(w)+αtΨ(w)+rt(w)\hat{h}_t(w) = f_t(w) + \alpha_t\Psi(w) + r_t(w);
  • αt\alpha_t — неубывающая последовательность;
  • Ψ(w)\Psi(w) — Centered регуляризатор с минимумом в точке w0w_0;
  • rt(w)r_t(w) — Proximal регуляризаторы;
  • rt(w)r_t(w) выбирается так, чтобы выражение h0:t^(w)=r0:t(w)+α1:tΨ(w)+f1:t(w)\hat{h_{0:t}}(w) = r_{0:t}(w) + \alpha_{1:t}\Psi(w) + f_{1:t}(w) было 1-сильно выпукло по отношению к некоторой норме t\vert\vert \cdot\vert\vert_t (возможно, своей на каждом шаге).

Тогда

  • Если мы рассматриваем regret относительно f^t(w)=ft(w)+αtΨ(w)\hat{f}_t(w) = f_t(w) + \alpha_t\Psi(w), то

RegretT(w)r0:T(w)+12t=1Tgtt,2;Regret_T(w^*) \leq r_{0:T}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{t,*}^2;

  • Если мы рассматриваем regret относительно ft(w)f_t(w), то

RegretT(w)r0:T(w)+α1:tΨ(w)+12t=1Tgtt,2,Regret_T(w^*) \leq r_{0:T}(w^*) + \alpha_{1:t}\Psi(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{t,*}^2,

где (t),\vert\vert \cdot\vert\vert_{(t),*} — норма, двойственная к норме t\vert\vert \cdot\vert\vert_{t}.

Обратите внимание. Оценки Proximal и General отличаются индексацией: до tt или до t1t-1 соответственно. Это чисто техническое различие, однако именно из-за него с Proximal регуляризаторами удобнее работать как в теоретических выкладках, так и при выведении практических методов.

Обратите внимание. На ft(w)f_t(w) мы не хотим накладывать ограничения сильной выпуклости, но сильную выпуклость функции h0:t(w)=f1:t(w)+r0:t(w)h_{0:t}(w) = f_{1:t}(w) + r_{0:t}(w) можно обеспечить за счет выбора сильно выпуклых регуляризаторов. В самом деле, сумма выпуклой и сильно выпуклой функций сильно выпукла. Если

ft(w)ft(wt)+(wwt)Tft(wt)f_t(w) \geq f_t(w_t) + (w - w_t)^T\nabla f_t(w_t)

и

rt(w)rt(wt)+(wwt)Trt(wt)+12wwt2,r_t(w) \geq r_t(w_t) + (w - w_t)^T\nabla r_t(w_t) + \frac{1}{2}\vert\vert w - w_t\vert\vert^2,

то

ft(w)+rt(w)ft(wt)+rt(wt)+(wwt)T(ft(wt)+rt(wt))+12wwt2.f_t(w) + r_t(w) \geq f_t(w_t) + r_t(w_t) + (w - w_t)^T(\nabla f_t(w_t) + \nabla r_t(w_t)) + \frac{1}{2}\vert\vert w - w_t\vert\vert^2.

Обратите внимание. Норма wt,2\vert\vert w\vert\vert_{t,*}^2 является сопряженной к норме, относительно которой 1-сильно выпукла функция h0:t(w)=f1:t(w)+r0:t(w)h_{0:t}(w) = f_{1:t}(w) + r_{0:t}(w). Это значит, что норму мы будем выбирать по сумме регуляризаторов r0:t(w)r_{0:t}(w), а не просто по rt(w)r_t(w).

Доказательство на примере теоремы 2

Нам понадобится следующая чисто техническая лемма, доказательство которой мы опустим. Желающие могут прочитать Appendix B в обзоре.

Lemma 7. Пусть

  • ϕ1\phi_1 — выпуклая функция RnR{}\mathbb{R}^n \rightarrow \mathbb{R} \cup \{\infty\}, для которой существует x1=argminxϕ1(x)x_1 = arg\min\limits_x \phi_1(x);
  • ψ\psi — выпуклая функция;
  • ϕ2(x)=ϕ1(x)+ψ(x)\phi_2(x) = \phi_1(x) + \psi(x) — выпуклая функция, для которой существует x2=argminxϕ2(x)x_2 = arg\min\limits_x \phi_2(x) и которая, кроме того, 1-сильно выпукла по норме \vert\vert \cdot\vert\vert.

Тогда, для любого элемента bb субдифференциала x1ψ\partial_{x_1} \psi имеет место неравенство

x1x2b\vert\vert x_1 - x_2\vert\vert \leq \vert\vert b\vert\vert_*

и для любого xx' имеет место неравенство

ϕ2(x1)ϕ2(x)12b.\phi_2(x_1) - \phi_2(x') \leq \frac{1}{2}\vert\vert b\vert\vert_*.

Доказательство теоремы 2

Рассмотрим соседние раунды wtw_t и wt+1w_{t+1}. Имеем

wt=argminwh0:t1=argminw[f1:t1+r0:t1]w_{t} = arg\min\limits_w h_{0:t-1} = arg\min\limits_w\left[f_{1:t-1} + r_{0:t-1}\right]

Обозначим ϕ1(w)=f1:t1(w)+r0:t(w)=h0:t1(w)+rt(w)=h0:t(w)ft(w)\phi_1(w) = f_{1:t-1}(w) + r_{0:t}(w) = h_{0:t-1}(w) + r_t(w) = h_{0:t}(w) - f_t(w). Поскольку wtw_t одновременно минимизирует и rt(w)r_t(w) (т.к. это proximal регуляризатор), и h0:t1h_{0:t-1}, имеем

wt=argminw[h0:t1+rt(w)]=argminwϕ1(w).w_t = arg\min\limits_w \Big[h_{0:t-1} + r_t(w)\Big] = arg\min\limits_w \phi_1(w).

Далее,

wt+1=argminwh0:t=argminw[ϕ1(w)+ft(w)]w_{t+1} = arg\min\limits_w h_{0:t} = arg\min\limits_w \Big[\phi_1(w) + f_t(w)\Big]

Выпишем оценку из Strong FTRL Lemma и постараемся оценить отмеченные рыжим слагаемые

t=1Tft(wt)f1:T(w)r0:T(w)+t=1Th0:t(wt)h0:t(wt+1)rt(wt)\sum\limits_{t=1}^Tf_t(w_t) - f_{1:T}(w^*) \leq r_{0:T}(w^*) + \color{#E06A27}{\sum\limits_{t=1}^Th_{0:t}(w_t) - h_{0:t}(w_{t+1}) - r_t(w_t)}

Так как по условию теоремы rt(wt)=0r_t(w_t) = 0, мы можем убрать это слагаемое:

h0:t(wt)h0:t(wt+1)rt(wt)=h0:t(wt)h0:t(wt+1)=h_{0:t}(w_t) - h_{0:t}(w_{t+1}) - r_t(w_t) = \color{#C81D6B}{h_{0:t}(w_t)} - \color{#348FEA}{h_{0:t}(w_{t+1})} =

=ϕ1(wt)+ft(wt)(ϕ1(wt+1)+ft(wt+1))= \color{#C81D6B}{\phi_1(w_t) + f_t(w_t)} - \color{#348FEA}{(\phi_1(w_{t+1}) + f_t(w_{t+1}))}

Обозначим ϕ2(w)=ϕ1(w)+ft(w)\phi_2(w) = \phi_1(w) + f_t(w). Применив Лемму 7, получаем

ϕ1(wt)+ft(wt)ϕ1(wt+1)ft(wt+1)12gtt,2\phi_1(w_t) + f_t(w_t) - \phi_1(w_{t+1}) - f_t(w_{t+1}) \leq \frac{1}{2}\vert\vert g_t\vert\vert_{t,*}^2

О связи оценок на regret для обычного и линеаризованного FTRL

Вспомним, что для линеаризованного FTRL имеет место неравенство:

RegretT(w)LinearizedRegretT(w).Regret_T(w) \leq LinearizedRegret_T(w).

Увы, верхняя оценка на левую часть неравенства не помогает оценить правую. Поэтому рассмотрим линеаризованный алгоритм более подробно. Он работает с последовательностью функций f^t(w)=gtTw\hat{f}_t(w) = g_t^Tw, где gtwtftg_t \in \partial_{w_t} f_t. Субдифференциал f^t\hat{f}_t состоит из одного вектора (градиента это функции)

g^t=f^t(w)w=gt\hat{g}_t = \frac{\partial \hat{f}_t(w)}{\partial w} = g_t

Применим приведённые выше оценки на regret для исходного и для линеаризованного алгоритма:

RegretT(w)r0:T(w)+12t=1Tgtt,2Regret_T(w^*) \leq r_{0:T}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{t,*}^2

LinearizedRegretT(w)r0:T(w)+12t=1Tg^tt,2=r0:T(w)+12t=1Tgtt,2LinearizedRegret_T(w^*) \leq r_{0:T}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert \hat{g}_t\vert\vert_{t,*}^2 = r_{0:T}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{t,*}^2

Легко убедиться, что оценки regret для обычного и линеаризованного FTRL совпадают и выполнено соотношение

RegretT(w)LinearizedRegretT(w)TheoremRegretT(w).Regret_T(w^*) \leq LinearizedRegret_T(w^*) \leq TheoremRegret_T(w^*).

Таким образом, для линеаризованного варианта любого алгоритма FTRL не нужно доказывать собственные оценки. А поскольку линеаризованный FTRL намного эффективнее, в дальнейшем мы всегда будем сразу переходить от исходного алгоритма к линеаризованному.

Построение эффективного адаптивного FTRL

Теперь, когда мы получили теоретические оценки на качество работы адаптивного FTRL, настала пора рассмотреть несколько конкретных примеров алгоритмов из этого класса.

Семейство квадратичных регуляризаторов rt(w)r_t(w)

Во всех дальнейших выкладках мы сразу ограничим себя семейством квадратичных регуляризаторов:

  1. Для FTRL-Centered алгоритмов: rt(w)=wTDtw=wDt2r_t(w) = w^TD_tw = \vert\vert w\vert\vert_{D_t}^2,
  2. Для FTRL-Proximal алгоритмов: rt(w)=(wwt)TDt(wwt)=wwtDt2r_t(w) = (w - w_t)^TD_t(w - w_t) = \vert\vert w - w_t\vert\vert_{D_t}^2,

где DtD_t — некоторая симметричная положительно определённая матрица (возможно, своя для каждого шага).

Помимо того, что они удобны и привычны, таки регуляризаторы позволяют достаточно просто выписывать оценки на regret. Чтобы в этом убедиться, вспомним, какие нетривиальные сущности возникают в теоремах:

  • на каждом шаге нам нужно выбрать норму t\vert\vert \cdot\vert\vert_{t}, по отношение к которой выражение h0:t(w)+ft+1(w)=r0:t(w)+f1:t+1(w)h_{0:t}(w) + f_{t+1}(w) = r_{0:t}(w) + f_{1:t+1}(w) было бы 1-сильно выпуклым;
  • во всех оценках участвует r0:T(w)r_{0:T}(w^*) (или r0:T1(w)r_{0:T-1}(w^*)), и его хорошо бы уметь оценивать сверху;
  • также в оценках фигурирует норма, двойственная к t\vert\vert \cdot\vert\vert_{t}, и её нужно уметь выводить.

Давайте разберёмся с каждым из пунктов и поймём, почему для квадратичных регуляризаторов всё довольно хорошо.

Выбор нормы t\vert\vert\cdot\vert\vert_{t}

Тут всё просто:

  1. Регуляризатор wD\vert\vert w\vert\vert_D является 1-сильно выпуклым относительно нормы wD\vert\vert w\vert\vert_D (т.е. относительно себя же);
  2. Регуляризатор wwtD\vert\vert w - w_t\vert\vert_D является 1-сильно выпуклым относительно той же самой нормы wD\vert\vert w\vert\vert_D.

Нам, впрочем, нужна 1-сильная выпуклость всей суммы r0:t(w)r_{0:t}(w), но легко убедиться, что r0:tr_{0:t} 1-сильно выпукло относительно суммарной нормы D0:t2\vert\vert \cdot\vert\vert_{D_{0:t}}^2. Поскольку D0:tD_{0:t} — тоже симметричная положительно определенная матрица, мы остаёмся в том же классе норм Махаланобиса.

Двойственная норма r0:t(w)r_{0:t}(w)

Оказывается, что

wD,=wD1\vert\vert w\vert\vert_{D,*} = \vert\vert w\vert\vert_{D^{-1}}

Доказательство

По определению

xD,=sup{xTy:yTDy1}\vert\vert x\vert\vert_{D,*} = sup \{ x^Ty: y^TDy \leq 1 \}

Для начала заметим, что ограничение-неравенство можно заменить на ограничение-равенство. А именно, если yD<1\vert\vert y\vert\vert_D < 1, то, взяв α>1:αyD=1\alpha > 1: \vert\vert \alpha y\vert\vert_D = 1, мы получим αxTy>xTy\vert\alpha x^Ty\vert > \vert x^Ty\vert. Значит, супремум можно искать на границе.

Далее, заметим, что мы работаем с конечномерными пространствами (вряд ли у вектора весов бесконечное число компонент), поэтому единичный шар yD=1\vert\vert y\vert\vert_D = 1 является компактом и, стало быть, супремум на нём достигается. Таким образом, мы можем решать привычную задачу оптимизации с ограничениями и применить для неё метод множителей Лагранжа.

Выпишем функцию Лагранжа:

L(y,λ)=xTyλ(yTDy1)L(y, \lambda) = x^Ty - \lambda(y^TDy - 1)

Продифференцируем её и приравняем градиент к нулю:

yL(y,λ)=x2λy(D+DT)=0\nabla_y L(y, \lambda) = x - 2\lambda y(D + D^T) = 0

Так как матрица DD симметрична, имеем D+DT=2DD + D^T = 2D и, следовательно,

y=1λD1xy = \frac{1}{\lambda}D^{-1}x

Подставим его в граничное условие-равенство и выразим λ\lambda:

1=yTDy=(1λD1x)TD(1λD1x)=1λ2xTDTDD1x1 = y^TDy = \left(-\frac{1}{\lambda}D^{-1}x\right)^TD\left(-\frac{1}{\lambda}D^{-1}x\right) =\frac{1}{\lambda^2}x^TD^{-T}DD^{-1}x

Отсюда

xTDTx=λ2x^TD^{-T}x = \lambda^2

Транспонировав обе части, получаем

xTD1x=λ2x^TD^{-1}x = \lambda^2

λ=xTD1x\lambda = \sqrt{x^TD^{-1}x}

Подставим найденное λ\lambda обратно в выражение y=1λD1xy = \frac{1}{\lambda}D^{-1}x:

y=D1xxTD1x,y = \frac{D^{-1}x}{\sqrt{x^TD^{-1}x}},

а полученное решение подставим в исходную функцию xTyx^Ty:

xTy=xTD1xxTD1x=xTD1x=xD1.x^Ty = \frac{x^TD^{-1}x}{\sqrt{x^TD^{-1}x}} = \sqrt{x^TD^{-1}x} = \vert\vert x\vert\vert_{D^{-1}}.

Ограничение сверху для r0:t(w)r_{0:t}(w^*)

Строго говоря, здесь никаких гарантий нет, и, например, очень плохая инициализация может всё сильно испортить. На практике, впрочем, всё работает нормально, но авторы статей не могут себе позволить надеяться на благосклонность судьбы. Поэтому в статьях часто встречается следующий костыль. Для вывода оценок на regret вводится регуляризатор r0(w)=IR(w)r_0(w) = I_{R}(w), где

IR(w)={w>R0wRI_{R}(w) = \begin{cases} \infty & \vert\vert w \vert\vert > R \\ 0 & \vert\vert w \vert\vert \leq R \end{cases}

это проекция на шар. Тогда можно доказать, что wR\vert\vert w^* \vert\vert \leq R.

Семейство логарифмических регуляризаторов

Для ряда частных задач вроде expert advice problem и оптимизаций по вероятностным распределениям используется также семейство энтропийных регуляризаторов

rt(w)=i=1Nwilogwir_t(w) = \sum\limits_{i=1}^Nw_i\log{w_i}

Более подробно о нём можно почитать в обзоре Shai-Shalev Schwartz, пример 2.5.

Constant learning rate FTRL

Простейший пример — это константный регуляризатор

rs(w)={12ηw22, s=0,0, s>0r_s(w) = \begin{cases} \frac{1}{2\eta}\vert\vert w\vert\vert_2^2,\ s=0,\\ 0,\ s > 0 \end{cases}

Легко показать, что 12ηw22=w12ηI2\frac{1}{2\eta}\vert\vert w\vert\vert_2^2 = \vert\vert w\vert\vert_{\frac{1}{2\eta}I}^2.

Соответствующий итерационный процесс оптимизации имеет вид

wt+1=argminw[g1:tTw+12ηw22]w_{t+1} = arg\min\limits_w\Big[ g_{1:t}^Tw + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\Big]

Как мы уже наблюдали ранее, этот метод эквивалентен методу стохастического градиентного спуска с константным learning rate. А именно, шаг обновления весов можно сформулировать двумя способами:

  • на языке FTRL: wt+1=ηg1:tTw_{t+1} = -\eta g_{1:t}^T;

  • на языке градиентного спуска: wt+1=wtηgtw_{t+1} = w_t - \eta g_t.

Оценка на Regret (3.1 Constant Learning Rate Online Gradient Descent). Пусть

  • gtG\vert\vert g_t\vert\vert \leq G;
  • wR\vert\vert w^*\vert\vert \leq R.

Тогда, если взять η=RGT\eta = \frac{R}{G\sqrt{T'}}, то для любого TTT' \leq T

RegretT(w)RGTRegret_T(w^*) \leq RG\sqrt{T'}

В целом, такая стратегия регуляризации не самая оптимальная. Интуитивно, наш регуляризатор фиксирован вне зависимости от того, сколько мы уже сыграли раундов, и со временем может перестать компенсировать член g1:tTwg_{1:t}^Tw, и тогда стабильность алгоритма может падать.

FTRL с learning rate scheduling

Чтобы исправить нестабильность алгоритма, возьмём L2L_2-регуляризатор, не равный нулю на каждом шаге.

Процесс оптимизации примет вид:

  • Для FTRL-Proximal: wt+1=argminw[g1:tTw+s=0tσs2wws22]w_{t+1} = arg\min\limits_w \Big[ g_{1:t}^Tw + \sum\limits_{s=0}^t\frac{\sigma_s}{2}\vert\vert w-w_s\vert\vert_2^2 \Big];
  • Для FTRL-Centered: wt+1=argminw[g1:tTw+s=0tσs2w22]w_{t+1} = arg\min\limits_w \Big[ g_{1:t}^Tw + \sum\limits_{s=0}^t\frac{\sigma_s}{2}\vert\vert w\vert\vert_2^2 \Big].

Посмотрим, какое обличье примет алгоритм FTRL-Proximal, если его изложить на языке градиентного спуска. Для этого продифференцируем и приравниваем нулю выражение, которое мы минимизируем:

0=g1:t+s=0tσs(wws)0 = g_{1:t} + \sum\limits_{s=0}^t\sigma_s (w - w_s)

s=0tσswsg1:t=σ0:tw\sum\limits_{s=0}^t\sigma_s w_s - g_{1:t} = \sigma_{0:t} w

wt+1=1σ0:ts=0tσsws1σ0:tg1:tw_{t+1} = \frac{1}{\sigma_{0:t}} \sum\limits_{s=0}^t\sigma_s w_s -\frac{1}{\sigma_{0:t}} g_{1:t}

Попробуем получить рекуррентную формулу для выражения wt+1w_{t+1} через wtw_t:

wt+1=1σ0:t(s=0tσswsg1:t)w_{t+1} = \frac{1}{\sigma_{0:t}} \Big(\sum\limits_{s=0}^t\sigma_s w_s - g_{1:t}\Big)

wt=1σ0:t1(s=0t1σswsg1:t1)w_t = \frac{1}{\sigma_{0:t-1}} \color{#E06A27}{\Big(\sum\limits_{s=0}^{t-1}\sigma_s w_s - g_{1:t-1}\Big)}

wt+1=1σ0:t(s=0t1σsws+σtwtg1:t1gt)w_{t+1} = \frac{1}{\sigma_{0:t}} \Big(\color{#E06A27}{\sum\limits_{s=0}^{t-1}\sigma_s w_s} + \sigma_t w_t - \color{#E06A27}{g_{1:t-1}} - g_t \Big)

wt+1=1σ0:t(σ0:t1wt+σtwtgt)=1σ0:t(σ0:twtgt)=wt1σ0:tgtw_{t+1} = \frac{1}{\sigma_{0:t}} \Big(\sigma_{0:t-1} w_t + \sigma_t w_t - g_t\Big) = \frac{1}{\sigma_{0:t}} \Big( \sigma_{0:t} w_t - g_t\Big) = w_t - \frac{1}{\sigma_{0:t}}g_t

Если теперь положить ηt=1σ0:t\eta_t = \frac{1}{\sigma_{0:t}}, мы получаем формулу градиентного спуска:

wt+1=wtηtgtw_{t+1} = w_t - \eta_t g_t

Таким образом, темп обучения градиентного спуска равен обратной сумме коэффициентов регуляризации ftrl. Точно так же можно выразить

σt=1ηt1ηt1\sigma_t = \frac{1}{\eta_t} - \frac{1}{\eta_{t-1}}

В качестве классической непокоординатной последовательности learning rate обычно берут

ηt=αt\eta_t = \frac{\alpha}{\sqrt{t}}

σt=t+1tα\sigma_t = \frac{\sqrt{t + 1} - \sqrt{t}}{\alpha}

Оценка на Regret (3.2, Dual Averaging) Пусть

  • gtG\vert\vert g_t\vert\vert \leq G,
  • wR\vert\vert w^*\vert\vert \leq R.

Тогда, если выбрать ηt=R2Gt+1\eta_t = \frac{R}{\sqrt{2}G\sqrt{t+1}}, то

RegretT(w)2RGTRegret_T(w^*) \leq \sqrt{2}RG\sqrt{T}

Как и в случае с константным learning rate, константа R2G\frac{R}{\sqrt{2}G} в ηt\eta_t на практике никому не известна, так что ее подменяют на α\alpha и перебирают руками с learning rate, равным αt+1\frac{\alpha}{\sqrt{t+1}}.

Data-Adaptive FTRL

До сих пор мы рассматривали в качестве нормы \vert\vert \cdot\vert\vert стандартное скалярное произведение, в которое различные компоненты вектора весов (которые, грубо говоря, соответствуют различным признакам) вносят равный вклад. Такой подход может быть слишком наивным для «боевых» задач, где геометрия оптимизации имеет форму, например, вытянутого эллипса.

Нетрудно обобщить предыдущие рассуждения на случай произвольного скалярного произведения

wt+1=argminw[g1:tTw+12s=0TwwsDs2]w_{t+1} = arg\min\limits_w\Big[ g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=0}^T\vert\vert w - w_s\vert\vert_{D_s}^2\Big]

Коэффициенты σs\sigma_s в этом выражении теперь спрятались в DsD_s. Найдем точку минимума:

0=g1:t+12s=0t(wws)(Ds+DsT)=g1:t+s=0t(wws)Ds0 = g_{1:t} + \frac{1}{2}\sum\limits_{s=0}^t(w - w_s)(D_s + D_s^T) = g_{1:t} + \sum\limits_{s=0}^t(w - w_s)D_s

(s=0tDs)w=s=0tDswsg1:t\Big(\sum\limits_{s=0}^tD_s\Big)w = \sum\limits_{s=0}^tD_sw_s - g_{1:t}

Но сразу возникают проблемы:

  • Нужно хранить s=0tDs\sum\limits_{s=0}^tD_s, в общем случае это квадрат по памяти от числа параметров. Ни в какой реальной задаче мы не сможем себе этого позволить;
  • На каждой итерации метода нужно решать гигантскую систему линейных уравнений для поиска ww. Есть все шансы состариться, так и не успев увидеть решение задачи оптимизации.

Упростим себе жизнь и предположим, что все матрицы DsD_s диагональны. Тогда s=1tDs\sum\limits_{s=1}^tD_s можно хранить в виде вектора диагональных элементов того же размера, что и ww, а система на каждой итерации будет решаться за линию.

AdaGrad: наилучший адаптивный метод

Разрешив себе брать нормы Ds\vert\vert\cdot\vert\vert_{D_s} с диагональными матрицами DsD_s, мы сделали алгоритм более гибким, но при этом приобрели дополнительные степени свободы (выбор диагональных элементов). Попробуем ответить на два вопроса:

  • Можно ли матрицы DsD_s не угадывать, а настраивать по доступной на очередном шаге информации?
  • Как выбирать матрицы DsD_s так, чтобы минимизировать оценки на regret?

В процессе поисков ответов на них мы придём к известному методу оптимизации AdaGrad.

Помня, что .D,=.D1\vert\vert .\vert\vert_{D,*} = \vert\vert .\vert\vert_{D^{-1}}, выпишем общий вид оценки на regret:

RegretT(w)r0:T1(w)+12t=1Tg(t),2=t=1TwwtDt2+12t=1Tgt(D0:T)12Regret_T(w^*) \leq r_{0:T-1}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g\vert\vert_{(t),*}^2 = \sum\limits_{t=1}^T \vert\vert w^* - w_t\vert\vert_{D_t}^2 + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{(D_{0:T})^{-1}}^2

Чтобы упростить выкладки, введем новую симметричную положительно определенную матрицу ST=D0:T1S_T = D_{0:T}^{-1} и перепишем формулы

RegretT(w)r0:T1(w)+12t=1Tgt1,2=t=1TwwtDt2+12t=1TgtST2Regret_T(w^*) \leq r_{0:T-1}(w^*) + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g\vert\vert_{t-1,*}^2 = \sum\limits_{t=1}^T \vert\vert w^* - w_t\vert\vert_{D_t}^2 + \frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{S_T}^2

С членом t=1TwwtDt2\sum\limits_{t=1}^T \vert\vert w^* - w_t\vert\vert_{D_t}^2 явно будет очень сложно работать: чтобы им пользоваться, нужно иметь на руках оптимальное решение wtw_t^* для всей предыдущей выборки. Более перспективным выглядит слагаемое 12t=1TgtST2\frac{1}{2}\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{S_T}^2: вычислять их одно удовольствие. Идея метода AdaGrad как раз в том, чтобы не пытаться работать с первым членом и минимизировать второй, надеясь, что итоговые оценки на regret при этом тоже улучшатся.

Для начала выведем диагональный AdaGrad как более простой случай. Если все DtD_t диагональны, то матрица ST=D1:T1S_T = D_{1:T}^{-1} тоже диагональна и представляется набором диагональных элементов 1si\frac{1}{s_i} (уберем индекс TT для сокращения выкладок, так как мы рассматриваем фиксированный раунд).

Распишем второе слагаемое в regret

t=1TgtST2=t=1Ti=1Ngt,i2si\sum\limits_{t=1}^T\vert\vert g_t\vert\vert_{S_T}^2 = \sum\limits_{t=1}^T\sum\limits_{i=1}^N\frac{g_{t,i}^2}{s_i}

Попробуем минимизировать его

{t=1Ti=1Ngt,i2siinfssi0\begin{cases}\sum\limits_{t=1}^T\sum\limits_{i=1}^N \frac{g_{t,i}^2}{s_i} \longrightarrow \inf\limits_s\\ s_i \geq 0 \end{cases}

Условие si0s_i \geq 0 возникает из неотрицательной определенности матрицы STS_T. Решеним такой задачи, очевидно, является si+s_i \rightarrow +\infty. Однако в этом случае член t=1TwwtDt2\sum\limits_{t=1}^T \vert\vert w^* - w_t\vert\vert_{D_t}^2 из оценки на regret станет, наоборот, бесконечно большим, и нужен какой-то компромисс. Введем довольно слабое ограничение на положительные коэффициенты

{t=1Ti=1Ngt,i2siinfssi0,i=1Nsic\begin{cases}\sum\limits_{t=1}^T\sum\limits_{i=1}^N \frac{g_{t,i}^2}{s_i} \longrightarrow \inf\limits_s\\ s_i \geq 0,\\ \sum\limits_{i=1}^Ns_i \leq c \end{cases}

и найдём оптимум с помощью метода множителей Лагранжа. Функция Лагранжа имеет вид

L(s,λ,θ)=t=1Ti=1Ngt,i2si+λTs+θ(i=1Nsic)L(s,\lambda,\theta) = \sum\limits_{t=1}^T\sum\limits_{i=1}^N \frac{g_{t,i}^2}{s_i} + \lambda^Ts + \theta\left(\sum\limits_{i=1}^Ns_i - c\right)

Отметим, что здесь λ\lambda — это вектор, а θ\theta — число.

Приравняем к нулю частные производные:

0=L(s,λ,θ)si=1sit=1Tgt,i2+λi+θ0=\frac{\partial L(s,\lambda,\theta)}{\partial s_i} = -\frac1{s_i}\sum\limits_{t=1}^T g_{t,i}^2 + \lambda_i + \theta

Вспомним про условия дополняющей нежесткости, требующие, чтобы λisi=0\lambda_i s_i = 0. Так как sis_i мы нулю приравнять здесь не можем, получаем, что λi=0\lambda_i = 0:

1sit=1Tgt,i2θ=0\frac1{s_i}\sum\limits_{t=1}^T g_{t,i}^2 - \theta = 0

si=θ12t=1Tgt,i2s_i = \theta^{-\frac{1}{2}}\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}

Теперь вспомним про условие i=1Nsic\sum\limits_{i=1}^Ns_i \leq c. Можно показать, что оптимум достигается на границе (то есть когда неравенство превращается в равенство). Тогда

c=i=1Nsi=θ12i=1Nt=1Tgt,i2c = \sum\limits_{i=1}^Ns_i = \theta^{-\frac{1}{2}}\sum\limits_{i=1}^N\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}

θ12=ci=1Nt=1Tgt,i2\theta^{-\frac{1}{2}} = \frac{c}{\sum\limits_{i=1}^N\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}}

si=ct=1Tgt,i2i=1Nt=1Tgt,i2s_i = \frac{c\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}}{\sum\limits_{i=1}^N\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}}

Вернемся к оценке на regret. Чему равно cc мы не знаем, поэтому мы просто констатируем, что оптимальные коэффициенты sis_i пропорциональны s=1tgs,i2\sqrt{\sum\limits_{s=1}^tg^2_{s,i}}:

si=1αt=1Tgt,i2s_i = \frac1{\alpha}\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}

Теперь STS_T — диагональная матрица с диагональными элементами 1si\frac1{s_i}. Следовательно, D0:T=(ST)1D_{0:T} = (S_T)^{-1} - тоже диагональная матрица с диагональными элементами sis_i:

D0:T,i=1αt=1Tgt,i2=t=1T(1αt=1Tgt,i21αt=1T1gt,i2)+0,D0=0,D_{0:T,i} = \frac1{\alpha}{\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}} = \sum\limits_{t=1}^T \left(\frac1{\alpha}{\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}} - \frac1{\alpha}{\sqrt{\sum\limits_{t=1}^{T-1} g_{t,i}^2}}\right) + 0, \quad D_0 = 0,

и легко убедиться, что

Dt,i=1αt=1Tgt,i21αt=1Tgt,i2D_{t,i} = \frac1{\alpha}{\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}} - \frac1{\alpha}{\sqrt{\sum\limits_{t=1}^T g_{t,i}^2}}

Теперь вспомним, что эти формулы в точности повторяют то, что мы получили выше для соотношения σt=1ηt1ηt1\sigma_t = \frac{1}{\eta_t} - \frac{1}{\eta_{t-1}}, только вместо общего коэффициента ηt\eta_t у нас теперь покоординатные коэффициенты ηt,i\eta_{t,i}:

ηt,i=αs=1tgs,i2\eta_{t,i} = \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t g_{s,i}^2}}

Получаем формулы для метода AdaGrad в градиентной постановке:

wt+1,i=wt,iαs=1tgs,i2gt,i,w_{t+1,i} = w_{t,i} - \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t g_{s,i}^2}}g_{t,i},

где коэффициент α\alpha приобретает значение learning rate.

Оценка на Regret (3.4, FTRL-Proximal with Diagonal Matrix Learning Rates)

Если использовать AdaGrad с покоординатными learning rate, то

RegretT(w)22Rt=1Tgt2Regret_T(w^*) \leq 2 \sqrt{2} R \sqrt{\sum\limits_{t=1}^Tg_t^2}

Отметим, что это оценка отличается от предыдущей тем, что вместо GTG\sqrt{T} используется t=1Tgt2\sqrt{\sum\limits_{t=1}^Tg_t^2}. Таким образом, если у градиента на какой-то из позиций стоит что-то большое, это повлияет лишь на одно из слагаемых под корнем вместо того, чтобы умножиться на T\sqrt{T}.

Эффективный размер шага. Предположим, что градиенты ограничены по норме g2R\vert\vert g\vert\vert_2 \leq R. Перепишем наши формулы в виде

αs=1Tgs,i2=αT1Ts=1Tgs,i2αRT\frac{\alpha}{\sqrt{\sum\limits_{s=1}^T g_{s,i}^2}} = \frac{\alpha}{\sqrt{T}\cdot\sqrt{\frac{1}{T}\sum\limits_{s=1}^T g_{s,i}^2}} \leq \frac{\alpha}{R\sqrt{T}}

Из этих формул следует, что в среднем learning rate в AdaGrad убывает как ηt=O(1T)\eta_t = O\left(\frac{1}{\sqrt{T}}\right), то есть так же, как в предыдущем методе. Отличие состоит лишь в более правильной покоординатной нормировке, которая улучшает сходимость.

Чтобы добавить в заметки выделенный текст, нажмите Command + E
Предыдущий параграф15.1. Введение в онлайн-обучение
Следующий параграф15.3. Регуляризация в онлайн-обучении

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.